二叉树_103二叉树的锯齿形层次遍历.md

题目描述：

给定一个二叉树，返回其节点值的锯齿形层序遍历。换句话说，先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

例如：

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其锯齿形层序遍历如下：

[ [3], [20,9], [15,7] ]

方法一: 递归

var zigzagLevelOrder = function(root) {
    let res = [];
    dfs(root, 0, res);
    return res;
};

function dfs(root, depth, res) {
    if (!root) return;
    if (!res[depth]) res[depth] = [];
    if (depth % 2 === 0) {
        res[depth].push(root.val);
    } else {
        res[depth].unshift(root.val);
    }
    dfs(root.left, depth + 1, res);
    dfs(root.right, depth + 1, res);
}

方法二：模拟队列 此题可以通过层序遍历的方式，记录每一层的节点值，然后判断当前层是奇数层还是偶数层，对于偶数层，将节点值数组进行翻转即可。

var zigzagLevelOrder = function(root) {
    if (!root) return [];
    let res = [];
    let deque = [];
    deque.push(root);
    let isOrderLeft = true;
    while (deque.length) {
        let levelList = [];
        let levelSize = deque.length;
        for (let i = 0; i < levelSize; i++) {
            if (isOrderLeft) {
                let node = deque.shift();
                levelList.push(node.val);
                if (node.left) deque.push(node.left);
                if (node.right) deque.push(node.right);
            } else {
                let node = deque.pop();
                levelList.push(node.val);
                if (node.right) deque.unshift(node.right);
                if (node.left) deque.unshift(node.left);
            }
        }
        res.push(levelList);
        isOrderLeft = !isOrderLeft;
    }
    return res;
};